home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / machserver / 1.098 / timer / timerQueue.c < prev    next >
C/C++ Source or Header  |  1990-12-07  |  15KB  |  560 lines
  1. /* 
  2.  * timerQueue.c --
  3.  *
  4.  *    Routines to handle interrupts from the timer chip.
  5.  *
  6.  *      The timer call back routine is called at every callback timer
  7.  *      interrupt. The callback timer is used to enable various modules of
  8.  *      the kernel to have routines called at a particular time in the
  9.  *      future.  For example, to run the "clock" paging algorithm once a
  10.  *      second, to see if a Fs_Select call has timed-out, etc.  The timer
  11.  *      queue can only be used by kernel modules because it is assumed
  12.  *      that the routines to be called exist in the system segment.  The
  13.  *      routines to be called are maintained on the timer queue.  The
  14.  *      callback timer is active only when the timer queue is not empty.
  15.  *
  16.  *
  17.  * Copyright 1986, 1988 Regents of the University of California
  18.  * Permission to use, copy, modify, and distribute this
  19.  * software and its documentation for any purpose and without
  20.  * fee is hereby granted, provided that the above copyright
  21.  * notice appear in all copies.  The University of California
  22.  * makes no representations about the suitability of this
  23.  * software for any purpose.  It is provided "as is" without
  24.  * express or implied warranty.
  25.  */
  26.  
  27. #ifndef lint
  28. static char rcsid[] = "$Header: /sprite/src/kernel/timer/RCS/timerQueue.c,v 9.5 90/10/13 17:05:43 mendel Exp $ SPRITE (Berkeley)";
  29. #endif not lint
  30.  
  31. #include "sprite.h"
  32. #include "timer.h"
  33. #include "timerInt.h"
  34. #include "sys.h"
  35. #include "sync.h"
  36. #include "sched.h"
  37. #include "list.h"
  38. #include "vm.h"
  39. #include "dev.h"
  40. #include "stdio.h"
  41. #include "bstring.h"
  42.  
  43.  
  44. /*
  45.  * Procedures internal to this file
  46.  */
  47.  
  48. void TimerDumpElement _ARGS_((Timer_QueueElement *timerPtr));
  49.  
  50.  
  51.  
  52. /* DATA STRUCTURES */
  53.  
  54. /*
  55.  *  The timer queue is a linked list of routines that need to be called at
  56.  *  certain times. TimerQueueList points to the head structure for the queue.
  57.  *
  58.  * >>>>>>>>>>>>>>>>>>>
  59.  * N.B. For debugging purposes, timerQueueList is global
  60.  *      so it can be accessed by routines outside this module.
  61.  * <<<<<<<<<<<<<<<<<<<
  62.  */ 
  63.  
  64. /* static */ List_Links    *timerQueueList;
  65.  
  66. /*
  67.  * The timer module mutex semaphore.  
  68.  */
  69.  
  70. Sync_Semaphore timerMutex;
  71.  
  72. /*
  73.  *  Debugging routine and data.
  74.  */
  75.  
  76. #ifdef DEBUG
  77. #define SIZE 500
  78. static unsigned char array[SIZE+1];
  79. static int count = 0;
  80. #endif DEBUG
  81.  
  82. /*
  83.  * Instrumentation for counting how many times the routines get called.
  84.  */
  85.  
  86. Timer_Statistics timer_Statistics;
  87.  
  88.  
  89.  
  90. /*
  91.  *----------------------------------------------------------------------
  92.  *
  93.  * Timer_Init --
  94.  *
  95.  *    Initializes the data structures necessary to manage the timer
  96.  *    queue of procedures.
  97.  *
  98.  * Results:
  99.  *     None.
  100.  *
  101.  * Side effects:
  102.  *     The timer queue structure is created and initialized.
  103.  *
  104.  *----------------------------------------------------------------------
  105.  */
  106.  
  107. void
  108. Timer_Init()
  109. {
  110.     static    Boolean    initialized    = FALSE;
  111.  
  112.     Sync_SemInitDynamic(&timerMutex,"Timer:timerMutex");
  113.  
  114.     if (initialized) {
  115.     printf("Timer_Init: Timer module initialized more that once!\n");
  116.     }
  117.     initialized = TRUE;
  118.  
  119.     TimerTicksInit();
  120.  
  121.     bzero((Address) &timer_Statistics, sizeof(timer_Statistics));
  122.  
  123.     timerQueueList = (List_Links *) Vm_BootAlloc(sizeof(List_Links));
  124.     List_Init(timerQueueList);
  125.  
  126.     /*
  127.      * Initialized the time of day clock.
  128.      */
  129.     TimerClock_Init();
  130.     Timer_TimerInit(TIMER_CALLBACK_TIMER);
  131.     Timer_TimerStart(TIMER_CALLBACK_TIMER);
  132. }
  133.  
  134.  
  135.  
  136. /*
  137.  *----------------------------------------------------------------------
  138.  *
  139.  *  Timer_CallBack --
  140.  *
  141.  *      This routine is called at every call back timer interrupt. 
  142.  *      It calls routines on the timer queue. 
  143.  *
  144.  *  Results:
  145.  *    None.
  146.  *
  147.  *  Side Effects:
  148.  *    Routines on the timer queue may cause side effects.
  149.  *
  150.  *----------------------------------------------------------------------
  151.  */
  152.  
  153. void
  154. Timer_CallBack(interval, time)
  155.     unsigned int interval;  /* Number of ticks since last invocation. */
  156.     Time   time;            /* Interval as time. */
  157. {
  158.     register List_Links    *readyPtr;    /* Ptr to TQE that's ready
  159.                          * to be called. */
  160.     Time            timeOfDay;    /* Best guess at tod. */
  161.     Timer_Ticks        currentSystemTimeTk;
  162.  
  163.     /*
  164.      *  The callback timer has expired. This means at least the first
  165.      *  routine on the timer queue is ready to be called.  Go through
  166.      *  the queue and call all routines that are scheduled to be
  167.      *  called. Since the queue is ordered by time, we can quit looking 
  168.      *  when we find the first routine that does not need to be called.
  169.      */
  170.  
  171. #ifdef GATHER_STAT
  172.     timer_Statistics.callback++;
  173. #endif
  174.  
  175.     MASTER_LOCK(&timer_ClockMutex);
  176.     Time_Add(timer_UniversalApprox, time, &timer_UniversalApprox);
  177.     timeOfDay = timer_UniversalApprox;
  178.     MASTER_UNLOCK(&timer_ClockMutex);
  179.  
  180.     if (vm_Tracing) {
  181.         Vm_StoreTraceTime(timeOfDay);
  182.     }
  183.     Sched_GatherProcessInfo(interval);
  184.     Dev_GatherDiskStats();
  185.  
  186.     MASTER_LOCK(&timerMutex);
  187.     if (!List_IsEmpty(timerQueueList)) {
  188.         Timer_GetCurrentTicks(¤tSystemTimeTk);
  189.         while (!List_IsEmpty(timerQueueList)) {
  190.         readyPtr = List_First(timerQueueList); 
  191.         if(Timer_TickGT(((Timer_QueueElement *)readyPtr)->time, 
  192.                   currentSystemTimeTk)) {
  193.             break;
  194.         } else {
  195.  
  196.             /*
  197.              *  First remove the item before calling it so the routine 
  198.              *  can call Timer_ScheduleRoutine to reschedule itself on 
  199.              *  the timer queue and not mess up the pointers on the 
  200.              *  queue.
  201.              */
  202.  
  203.             List_Remove(readyPtr);
  204.  
  205.             /*
  206.              *  Now call the routine.  It is interrupt time and 
  207.              *  the routine must do as little as possible.  The 
  208.              *  routine is passed the time it was scheduled to 
  209.              *  be called at and a client-specified argument.
  210.              * 
  211.              *  We release the timerMutex during the call backs to
  212.              *    prevent the many deadlocks that can occur on a 
  213.              *    multiprocessor.
  214.              */
  215.  
  216. #define  ELEMENTPTR ((Timer_QueueElement *) readyPtr)
  217.  
  218.             if (ELEMENTPTR->routine == 0) {
  219.             panic("Timer_ServiceInterrupt: t.q.e. routine == 0\n");
  220.             } else {
  221.             void        (*routine) _ARGS_((Timer_Ticks timeTicks,
  222.                               ClientData  clientData));
  223.             Timer_Ticks timeTk;
  224.             ClientData  clientData;
  225.  
  226.             ELEMENTPTR->processed = TRUE;
  227.             routine = ELEMENTPTR->routine;
  228.             timeTk = ELEMENTPTR->time;
  229.             clientData = ELEMENTPTR->clientData;
  230.             MASTER_UNLOCK(&timerMutex);
  231.             (routine) (timeTk, clientData);
  232.             MASTER_LOCK(&timerMutex);
  233.             }
  234.         }
  235.         }
  236. #undef  ELEMENTPTR
  237.  
  238.  
  239.     } 
  240.     MASTER_UNLOCK(&timerMutex);
  241.     
  242. }
  243.  
  244.  
  245. /*
  246.  *----------------------------------------------------------------------
  247.  *
  248.  * Timer_ScheduleRoutine --
  249.  *
  250.  *    Schedules a routine to be called at a certain time by adding 
  251.  *    it to the timer queue. A routine is specified using a
  252.  *    Timer_QueueElement structure, which is described in timer.h.
  253.  *
  254.  *    When the client routine is called at its scheduled time, it is 
  255.  *    passed two parameters:
  256.  *     a) the time it is scheduled to be called at, and
  257.  *     b) uninterpreted data.
  258.  *    Hence the routine should be declared as:
  259.  *
  260.  *        void
  261.  *        ExampleRoutine(time, data)
  262.  *        Timer_Ticks time;
  263.  *        ClientData data;
  264.  *        {}
  265.  *
  266.  *
  267.  *    The time a routine should be called at can be specified in two
  268.  *    ways: an absolute time or an interval. For example, to have 
  269.  *    ExampleRoutine called in 1 hour, the timer queue element would 
  270.  *    be setup as:
  271.  *        Timer_QueueElement    element;
  272.  *
  273.  *        element.routine    = ExampleRoutine;
  274.  *        element.clientData    = (ClientData) 0;
  275.  *        element.interval    = timer_IntOneHour;
  276.  *        Timer_ScheduleRoutine(&element, TRUE);
  277.  *
  278.  *    The 2nd argument (TRUE) to Timer_ScheduleRoutine means the routine
  279.  *    will be called at the interval + the current time.
  280.  *
  281.  *      Once ExampleRoutine is called, it can schedule itself to be
  282.  *      called again using Timer_ScheduleRoutine().   
  283.  *
  284.  *        Timer_ScheduleRoutine(&element, TRUE);
  285.  *
  286.  *    The 2nd argument again means schedule the routine relative to the
  287.  *    current time. Since we still want ExampleRoutine to be called in
  288.  *    an hour, we don't have to change the interval field in the timer
  289.  *    queue element.
  290.  *      Obviously, the timer queue element has to be accessible 
  291.  *    to ExampleRoutine.
  292.  *
  293.  *    If we want ExampleRoutine to be called at a specific time, say
  294.  *    March 1, 1986, the time field in the t.q. element must be set:
  295.  *
  296.  *        element.routine    = ExampleRoutine;
  297.  *        element.clientData    = (ClientData) 0;
  298.  *        element.time    = march1;
  299.  *        Timer_ScheduleRoutine(&element, FALSE);
  300.  *
  301.  *    (Assume march1 has the appropriate value for the date 3/1/86.)
  302.  *
  303.  * Results:
  304.  *    None.
  305.  *
  306.  * Side effects:
  307.  *    The timer queue element is added to the timer queue.
  308.  *
  309.  *----------------------------------------------------------------------
  310.  */
  311.  
  312. void
  313. Timer_ScheduleRoutine(newElementPtr, interval)
  314.     register    Timer_QueueElement *newElementPtr; /* routine to be added */
  315.     Boolean    interval;    /* TRUE if schedule relative to current time. */
  316. {
  317.     register List_Links     *itemPtr;
  318.     Boolean inserted;        /* TRUE if added to Q in FORALL loop. */
  319.  
  320.     MASTER_LOCK(&timerMutex); 
  321.     /*
  322.      *  Go through the timer queue and insert the new routine.  The queue
  323.      *  is ordered by the time field in the element.  The sooner the
  324.      *  routine needs to be called, the closer it is to the front of the
  325.      *  queue.  The new routine will not be added to the queue inside the
  326.      *  FOR loop if its scheduled time is after all elements in the queue
  327.      *  or the queue is empty.  It will be added after the last element in
  328.      *  the queue.
  329.      */
  330.  
  331.     inserted = FALSE;  /* assume new element not inserted inside FOR loop.*/
  332.  
  333. #ifdef GATHER_STAT
  334.     timer_Statistics.schedule++;
  335. #endif
  336.  
  337.     /*
  338.      * Safety check.
  339.      */
  340.     if (newElementPtr->routine == 0) {
  341.     panic("Timer_ScheduleRoutine: bad address for t.q.e. routine.\n");
  342.     }
  343.  
  344.     /* 
  345.      *  Reset the processed flag. It is used by the client to see if 
  346.      *  the routine is being called from the timer queue. This flag is
  347.      *  necessary because the client passes in the timer queue element
  348.      *  and it may need to examine the element to determine its status.
  349.      */
  350.     newElementPtr->processed = FALSE;
  351.  
  352.     /*
  353.      * Convert the interval into an absolute time by adding the 
  354.      * interval to the current time.
  355.      */
  356.     if (interval) {
  357.     Timer_Ticks currentTime;
  358.     Timer_GetCurrentTicks(¤tTime);
  359.     Timer_AddIntervalToTicks(currentTime, newElementPtr->interval,
  360.                        &(newElementPtr->time));
  361.     }
  362.  
  363.     List_InitElement((List_Links *) newElementPtr);
  364.  
  365.     LIST_FORALL(timerQueueList, itemPtr) {
  366.  
  367.        if (Timer_TickLT(newElementPtr->time, 
  368.        ((Timer_QueueElement *)itemPtr)->time)) {
  369.         List_Insert((List_Links *) newElementPtr, LIST_BEFORE(itemPtr));
  370.         inserted = TRUE;
  371.         break;
  372.     }
  373.     }
  374.  
  375.     if (!inserted) {
  376.     List_Insert((List_Links *) newElementPtr, LIST_ATREAR(timerQueueList));
  377.     }
  378.     MASTER_UNLOCK(&timerMutex); 
  379. }
  380.  
  381.  
  382. /*
  383.  *----------------------------------------------------------------------
  384.  *
  385.  * Timer_DescheduleRoutine --
  386.  *
  387.  *    Deschedules a routine to be called at a certain time by removing 
  388.  *    it from the timer queue.
  389.  *
  390.  *    Note that Timer_DescheduleRoutine does NOT guarantee that the 
  391.  *    routine to be descheduled will not be called, only that the 
  392.  *    routine will not be on the timer queue when Timer_DescheduleRoutine 
  393.  *    returns.
  394.  *
  395.  *    If Timer_DescheduleRoutine is able to obtain the timer mutex before
  396.  *    the timer interrupts, the routine will be removed from the
  397.  *    timer queue before the interrupt handler has a chance to call it.
  398.  *    If the interrupt handler is able to obtain the timer mutex before
  399.  *    Timer_DescheduleRoutine, then the interrupt handler will remove and 
  400.  *    call the routine before Timer_DescheduleRoutine has a chance 
  401.  *    to remove it.
  402.  *
  403.  * Results:
  404.  *    TRUE if the element was removed, FALSE if it was already gone.
  405.  *
  406.  * Side effects:
  407.  *    The timer queue structure is updated. 
  408.  *
  409.  *----------------------------------------------------------------------
  410.  */
  411.  
  412. Boolean
  413. Timer_DescheduleRoutine(elementPtr)
  414.     register Timer_QueueElement *elementPtr;    /* routine to be removed */
  415. {
  416.     register List_Links     *itemPtr;
  417.  
  418. #ifdef GATHER_STAT
  419.     timer_Statistics.desched++;
  420. #endif
  421.     Boolean foundIt = FALSE;
  422.  
  423.     /*
  424.      *  Go through the timer queue and remove the routine.  
  425.      */
  426.  
  427.     MASTER_LOCK(&timerMutex); 
  428.  
  429.     LIST_FORALL(timerQueueList, itemPtr) {
  430.  
  431.     if ((List_Links *) elementPtr == itemPtr) {
  432.         List_Remove(itemPtr);
  433.         foundIt = TRUE;
  434.         break;
  435.     }
  436.     }
  437.  
  438.     MASTER_UNLOCK(&timerMutex);
  439.     return(foundIt);
  440. }
  441.  
  442. /*
  443.  *----------------------------------------------------------------------
  444.  *
  445.  * Timer_DumpQueue --
  446.  *
  447.  *    Output the timer queue on the display.
  448.  *
  449.  * Results:
  450.  *    None.
  451.  *
  452.  * Side effects:
  453.  *    Output is written to the display.
  454.  *
  455.  *----------------------------------------------------------------------
  456.  */
  457.  
  458. /*ARGSUSED*/
  459. void
  460. Timer_DumpQueue(data)
  461.     ClientData    data;    /* Not used. */
  462. {
  463.     Timer_Ticks    ticks;
  464.     Time    time;
  465.     List_Links *itemPtr;
  466.  
  467.     Timer_GetCurrentTicks(&ticks);
  468.     Timer_TicksToTime(ticks, &time);
  469.     printf("Now: %d.%06u sec\n", time.seconds, time.microseconds);
  470.  
  471.     if (List_IsEmpty(timerQueueList)) {
  472.     printf("\nList is empty.\n");
  473.     } else {
  474.     printf("\n");
  475.  
  476.     MASTER_LOCK(&timerMutex); 
  477.  
  478.     LIST_FORALL(timerQueueList, itemPtr) {
  479.         TimerDumpElement((Timer_QueueElement *) itemPtr);
  480.     }
  481.  
  482.     MASTER_UNLOCK(&timerMutex); 
  483.  
  484.     }
  485. }
  486.  
  487. /*
  488.  *----------------------------------------------------------------------
  489.  *
  490.  * TimerDumpElement --
  491.  *
  492.  *    Output the more important parts of a Timer_QueueElement on the display.
  493.  *
  494.  * Results:
  495.  *    None.
  496.  *
  497.  * Side effects:
  498.  *    Output is written to the display.
  499.  *
  500.  *----------------------------------------------------------------------
  501.  */
  502.  
  503. void
  504. TimerDumpElement(timerPtr)
  505.     Timer_QueueElement *timerPtr;
  506. {
  507.     Time      time;
  508.  
  509.     Timer_TicksToTime(timerPtr->time, &time);
  510.  
  511.     printf("(*0x%x)(0x%x) @ %d.%06u\n",
  512.         (Address) timerPtr->routine, 
  513.         (Address) timerPtr->clientData,
  514.         time.seconds, time.microseconds);
  515. }
  516.  
  517. /*
  518.  *----------------------------------------------------------------------
  519.  *
  520.  * Timer_DumpStats --
  521.  *
  522.  *    Initializes and prints the timer module statistics.
  523.  *
  524.  * Results:
  525.  *    None.
  526.  *
  527.  * Side effects:
  528.  *    Output is written to the display.
  529.  *
  530.  *----------------------------------------------------------------------
  531.  */
  532. void
  533. Timer_DumpStats(arg)
  534.     ClientData    arg;
  535. {
  536.     static   Timer_Ticks    start;
  537.     static   Timer_Ticks    end;
  538.     Timer_Ticks    diff;
  539.     Time      time;
  540.  
  541.     if (arg ==  (ClientData) 's') {
  542.     Timer_GetCurrentTicks(&start);
  543.     bzero((Address) &timer_Statistics,sizeof(timer_Statistics));
  544.     } else {
  545.     Timer_GetCurrentTicks(&end);
  546.     Timer_SubtractTicks(end, start, &diff);
  547.     Timer_TicksToTime(diff, &time);
  548.  
  549.     printf("\n%d.%06d cb %d prof %d spur %d; Sched %d Res %d Des %d\n",
  550.         time.seconds, time.microseconds,
  551.         timer_Statistics.callback,
  552.         timer_Statistics.profile,
  553.         timer_Statistics.spurious,
  554.         timer_Statistics.schedule,
  555.         timer_Statistics.resched,
  556.         timer_Statistics.desched
  557.     );
  558.     }
  559. }
  560.